package LimitedTimeGame.Day_0302;

/**
 * @author zxc
 * @date 2023/03/02 09:10
 **/

import java.util.PriorityQueue;

/**
 * 题目 ：滑动窗口的最大值
 * 题目详述 ：
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。
 * 滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 *
 * 提示：
 * 1 <= nums.length <= 10^5
 * -10^4 <= nums[i] <= 10^4
 * 1 <= k <= nums.length
 *
 */
public class MaxSlidingWindow {
    public static void main(String[] args) {
        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }
    /**
     * 思路 ：
     * ===》
     * （1）优先队列（最大堆/最小堆），即通过存储 nums数组中元素 && 该元素对应的下标;
     *  ===》
     *  优先队列的排序顺序 ：根据所存储的nums数组元素大小，从大到小进行排序 && 若是元素相同的话，则根据下标进行从大到小进行排序;
     * （2）首先，将nums数组的前k个元素加入到 优先队列中;
     * （3）其次，后续每次添加元素到该优先队列中后，需要去判断 堆顶元素是否在滑动窗口之内;
     *  ===》即，代表当前堆顶元素所对应的最大元素，已经在滑动窗口右移过程中，超出滑动窗口范围;
     * （4）若是堆顶元素已经不在滑动窗口之内的话，则直接将堆顶元素弹出;
     *  ===》直至堆顶元素在滑动窗口之内，则将其加入到result结果数组中;
     *
     *  ===》
     *  （1）需要注意的是，Heap中，poll()操作的时间复杂度为O（1）;而对比之下，remove()方法的操作时间复杂度为O（n）;
     *  （2）使用堆，可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn);
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        // 优先队列的排序顺序 ：
        // 根据所存储的nums数组元素大小，从大到小进行排序 && 若是元素相同的话，则根据下标进行从大到小进行排序;
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((p1 , p2) -> {
            return p2[0] == p1[0] ? p2[1] - p1[1] : p2[0] - p1[0];
        });
        for(int i = 0 ; i < k ; i++){
            maxHeap.offer(new int[]{nums[i] , i});
        }
        result[0] = maxHeap.peek()[0];
        for(int i = k ; i < len ; i++){
            maxHeap.offer(new int[]{nums[i] , i});
            // 若是优先队列/最大堆的堆顶元素 不在滑动窗口范围内，则直接从优先队列中进行删除
            // while循环结束条件 ：即，当优先队列/最大堆的堆顶元素 在滑动窗口之内的话，则将该元素加入到result结果数组中;
            while (maxHeap.peek()[1] <= i - k){
                maxHeap.poll();
            }
            result[i - k + 1] = maxHeap.peek()[0];
        }
        return result;
    }
}
